// 剑指 Offer 07. 重建二叉树
// 输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。

// 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

 

// 示例 1:


// Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
// Output: [3,9,20,null,null,15,7]
// 示例 2:

// Input: preorder = [-1], inorder = [-1]
// Output: [-1]
 

// 限制：

// 0 <= 节点个数 <= 5000

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
    	return build(preorder, 0, preorder.size() - 1,
    				 inorder, 0, inorder.size() - 1);
    }

    TreeNode* build(vector<int>& preorder, int preStart, int preEnd,
    				vector<int>& inorder, int inStart, int inEnd) {
    	if(preStart > preEnd)
    		return NULL;

    	int rootVal = preorder[preStart];

    	int index;
    	for(int i = inStart; i < inEnd; ++i) {
    		if(inorder[i] == rootVal) {
    			index = i;
    			break;
    		}
    	}

    	TreeNode *root = new TreeNode(rootVal);
    	int leftSize = index - inStart;

    	root->left = build(preorder, preStart + 1, preStart + leftSize,
    						inorder, inStart, index - 1);

    	root->right = build(preorder, preStart + leftSize + 1, preEnd,
    						inorder, index + 1, inEnd);

    	return root;
    }
};